23. 合并K个升序链表

// 给你一个链表数组，每个链表都已经按升序排列。
// 请你将所有链表合并到一个升序链表中，返回合并后的链表
class MiniHeap {
  constructor() {
    this.heap = [];
  }

  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
    // [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  getParentIndex(i) {
    return (i - 1) >> 1; // 二进制向右移动一位 表示 / 2
  }

  getLeftIndex(i) {
    return i * 2 + 1;
  }

  getRightIndex(i) {
    return i * 2 + 2;
  }

  // 往上升
  shiftUp(index) {
    if (index === 0) return; // 到顶部暂停
    const parentIndex = this.getParentIndex(index); // 获取父级索引
    if (this.heap[parentIndex].val > this.heap[index].val) {
      // 当前值大于父级索引
      this.swap(index, parentIndex); // 交换位置
      this.shiftUp(parentIndex); // 继续往上
    }
  }
  // 往下降
  shiftDown(i) {
    const leftIndex = this.getLeftIndex(i); // 查询左子树索引
    const rightIndex = this.getRightIndex(i); // 查询右子树索引
    if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[i].val) {
      // 索引大于左子树互换位置
      this.swap(leftIndex, i);
      this.shiftDown(leftIndex);
    }
    if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[i].val) {
      // 索引大于右子树互换位置
      this.swap(rightIndex, i);
      this.shiftDown(rightIndex);
    }
  }

  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  // 删除堆顶
  pop() {
    if (this.size() === 1) return this.heap.shift();
    // 不能直接删除堆顶, 可能会造成堆顶不是最小值, 将尾部移动到堆顶做替换, 并执行向下降 动态将最小值移动到堆顶
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return top;
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }
}

var mergeKLists = function(lists) {
  let prevLine = null;

  for (let i = 0; i < lists.length; i++) {
    prevLine = merge2List(prevLine, lists[i]);
  }

  return prevLine;
};

function merge2List(l1, l2) {
  const headLine = {};
  let head = headLine;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      head.next = l1;
      l1 = l1.next;
    } else {
      head.next = l2;
      l2 = l2.next;
    }
    head = head.next;
  }

  head.next = l1 === null ? l2 : l1;

  return headLine.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists.length) return [];
  const minHeap = new MiniHeap();
  for (let i = 0; i < lists.length; i++) {
    lists[i] && minHeap.insert(lists[i]);
  }

  const head = new ListNode();
  let p = head;

  while (minHeap.size()) {
    const h = minHeap.pop();
    p.next = h;
    p = p.next;
    h.next && minHeap.insert(h.next);
  }
  return head.next;
};

const lists = [
  { val: 1, next: { val: 4, next: { val: 5, next: null } } },
  { val: 1, next: { val: 3, next: { val: 4, next: null } } },
  { val: 2, next: { val: 6, next: null } },
];

console.log(JSON.stringify(mergeKLists(lists)));
console.log(JSON.stringify(mergeKLists([[]])));
console.log(JSON.stringify(mergeKLists([])));